package com.hanxiaozhang.no3algorithm.recursion;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * 功能描述: <br>
 * 〈〉
 * 给一个数组：[1, 2, 2]，找出所有子数组，例如这个数组的子数组有：[], [1], [2], [1, 2], [2, 2], [1, 2, 2]
 * 思路：
 * 巧用递归求字符串的子集
 * 求子集，每一位都只有两种状态，在子集中或不在子集中。那把每种情况都输出就可以了
 *
 * @Author:hanxinghua
 * @Date: 2019/3/10
 */

public class No2FindSubArray {

    static Set<List<Integer>> set = new HashSet<>();

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 3};
        // 声名一个长度为arr.length的布尔数组，数组元素全部为false
        boolean[] booleans = new boolean[arr.length];
        find(arr, 0, booleans);
        System.out.println("数组的子数组: " + set);
    }


    /**
     * 递归方法
     *
     * @param arr      数组
     * @param position 当前位置
     * @param isIns
     */
    private static void find(int[] arr, int position, boolean[] isIns) {
        // position == arr.length时，证明该种情况已完成吗，需要汇总
        if (position == arr.length) {
            List<Integer> list = new LinkedList<>();
            for (int i = 0; i < arr.length; i++) {
                if (isIns[i]) {
                    list.add(arr[i]);
                }
            }
            System.out.println("每次组合结果: " + list);
            set.add(list);
        } else {
            isIns[position] = true;
            find(arr, position + 1, isIns);
            isIns[position] = false;
            find(arr, position + 1, isIns);
        }
    }


}
